home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / c / hce.lha / HCE / HCESource / TOP / Source / branch.c next >
Encoding:
C/C++ Source or Header  |  1992-09-02  |  12.2 KB  |  542 lines
  1. /* Copyright (c) 1988,1991 by Sozobon, Limited.  Author: Tony Andrews
  2.  *
  3.  * Permission is granted to anyone to use this software for any purpose
  4.  * on any computer system, and to redistribute it freely, with the
  5.  * following restrictions:
  6.  * 1) No charge may be made other than reasonable charges for reproduction.
  7.  * 2) Modified versions must be clearly marked as such.
  8.  * 3) The authors are not responsible for any harmful consequences
  9.  *    of using this software, even if they result from defects in it.
  10.  *
  11.  * Modified by Detlef Wuerkner for AMIGA
  12.  * Changes marked with TETISOFT
  13.  */
  14. #include "top.h"
  15.  
  16. #define    TOUCHED(bp)    ((bp)->flags & B_TOUCHED)
  17.  
  18. /*
  19.  * bcomp(bc) - return the complement of the given branch code
  20.  *
  21.  * Used when a branch reversal is needed.
  22.  */
  23. static    int
  24. bcomp(bc)
  25. register int    bc;
  26. {
  27.     switch (bc) {
  28.     case BHI: return BLS;
  29.     case BLS: return BHI;
  30.     case BCC: return BCS;
  31.     case BCS: return BCC;
  32.     case BNE: return BEQ;
  33.     case BEQ: return BNE;
  34.     case BVC: return BVS;
  35.     case BVS: return BVC;
  36.     case BPL: return BMI;
  37.     case BMI: return BPL;
  38.     case BGE: return BLT;
  39.     case BLT: return BGE;
  40.     case BGT: return BLE;
  41.     case BLE: return BGT;
  42.     default:
  43.         fprintf(stderr, "bcomp() - bad branch code %d\n", bc);
  44.  
  45. /* CHANGED BY TETISOFT */
  46. /*        exit(1); */
  47.         exit(EXIT_FAILURE);
  48.  
  49.     }
  50. }
  51.  
  52. /*
  53.  * isbranch(s) - determines if 's' is a branch opcode
  54.  *
  55.  * Returns 1 for branches whose destination is the first operand,
  56.  * and 2 for branches whose dest. is the second.
  57.  */
  58. static    int
  59. isbranch(c)
  60. register int    c;
  61. {
  62.     switch (c) {
  63.     case BRA: case BHI: case BLS: case BCC:
  64.     case BCS: case BNE: case BEQ: case BVC:
  65.     case BVS: case BPL: case BMI: case BGE:
  66.     case BLT: case BGT: case BLE:
  67.         return 1;
  68.  
  69.     case DBRA: case DBHI: case DBLS: case DBCC:
  70.     case DBCS: case DBNE: case DBEQ: case DBMI:
  71.     case DBGE: case DBLT: case DBGT: case DBLE:
  72.     case  DBT:
  73.         return 2;
  74.  
  75.     default:
  76.         return 0;
  77.     }
  78. }
  79.  
  80. /*
  81.  * cblock(cp) - return the first block containing some code
  82.  *
  83.  * Starting with 'cp', find a block that has one or more instructions
  84.  * in it. This is useful to collapse multiple null blocks into a single
  85.  * logical point. This happens at points in the generated code where
  86.  * there are multiple labels at the same logical location.
  87.  */
  88. static    BLOCK *
  89. cblock(bp)
  90. register BLOCK    *bp;
  91. {
  92.     while (bp->first == NULL && bp->bcond == NULL) {
  93.         if (bp->bfall == NULL) {
  94.             fprintf(ofp, "cblock() - error in block %s\n",
  95.                 bp->name);
  96.  
  97. /* CHANGED BY TETISOFT */
  98. /*            exit(1); */
  99.             exit(EXIT_FAILURE);
  100.  
  101.         }
  102.         bp = bp->bfall;
  103.     }
  104.  
  105.     return bp;
  106. }
  107.  
  108. /*
  109.  * bsplit() - split up blocks with branches inside them
  110.  *
  111.  * Look for branch instructions in each block. If somewhere in the middle of
  112.  * the block, split up the block. When done, the blocks are broken down into
  113.  * true basic blocks.
  114.  */
  115. static    void
  116. bsplit(bp)
  117. BLOCK    *bp;
  118. {
  119.     register BLOCK    *cp;    /* the current block */
  120.     register BLOCK    *np;    /* new block (if needed) */
  121.     register INST    *ip;    /* current instruction */
  122.  
  123.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  124.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  125.             if (isbranch(ip->opcode) && ip->next != NULL) {
  126.                 np = mksym(mktmp());
  127.  
  128.                 np->chain = cp->chain;
  129.                 cp->chain = np;
  130.  
  131.                 np->next = cp->next;
  132.                 cp->next = np;
  133.  
  134.                 np->first = ip->next;
  135.                 np->first->prev = NULL;
  136.                 np->last = cp->last;
  137.  
  138.                 cp->last = ip;
  139.                 cp->last->next = NULL;
  140.  
  141.             } else if (ip->opcode == DC) {
  142.                 BLOCK    *db;
  143.  
  144.                 /*
  145.                  * If the instruction is part of a branch
  146.                  * table, both the current block and the
  147.                  * destination need to be marked as "reached".
  148.                  */
  149.                 cp->flags |= B_ISREACHED;
  150.  
  151.                 if ((db = getsym(ip->src.astr)) != NULL)
  152.                     db->flags |= B_ISREACHED;
  153.                 else {
  154.                     fprintf(stderr,
  155.                       "bsplit() - symbol '%s' not found\n",
  156.                       ip->src.astr);
  157.  
  158. /* CHANGED BY TETISOFT */
  159. /*                    exit(1); */
  160.                     exit(EXIT_FAILURE);
  161.  
  162.                 }
  163.             }
  164.         }
  165.     }
  166. }
  167.  
  168. /*
  169.  * bfix() - fix up the branch pointers
  170.  *
  171.  * Go through each block setting up 'bcond' and 'bfall' properly. If the
  172.  * last instruction in the block is an unconditional branch, remove it
  173.  * and set 'bfall' instead. The idea is that there should be no branch
  174.  * instructions left when we're done. We remember the logical effect of
  175.  * each branch, but reconstruct the branches later in a more optimal way.
  176.  */
  177. static    void
  178. bfix(bp)
  179. register BLOCK    *bp;
  180. {
  181.     register BLOCK    *cp;    /* current block */
  182.     register INST    *ip;    /* current instruction */
  183.  
  184.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  185.  
  186.         /* no instructions in the block */
  187.         if (cp->first == NULL) {
  188.             cp->bcond = NULL;
  189.             cp->bfall = cp->next;
  190.             continue;
  191.         }
  192.  
  193.         /* the last instruction is a "return" */
  194.         if (cp->last->opcode == RTS) {
  195.             cp->bcond = cp->bfall = NULL;
  196.             cp->flags |= B_RET;
  197.             continue;
  198.         }
  199.  
  200.         /* the last instruction isn't a branch */
  201.         if (!isbranch(cp->last->opcode)) {
  202.             cp->bcond = NULL;
  203.             cp->bfall = cp->next;
  204.             continue;
  205.         }
  206.  
  207.         /*
  208.          * If we reach this point, then we've got a branch we need
  209.          * to remove at the end of this block.
  210.          */
  211.         cp->bfall = cp->next;
  212.         if (isbranch(cp->last->opcode) == 1) {
  213.             cp->bcode = cp->last->opcode;
  214.             cp->bcond = getsym(cp->last->src.astr);
  215.         } else {
  216.             cp->bcode = -1;
  217.             cp->bcond = getsym(cp->last->dst.astr);
  218.         }
  219.  
  220.         if (cp->bcond == NULL) {
  221.             fprintf(stderr, "top: branch to bad label '%s'\n",
  222.                 cp->last->src.astr);
  223.  
  224. /* CHANGED BY TETISOFT */
  225. /*            exit(1); */
  226.             exit(EXIT_FAILURE);
  227.  
  228.         }
  229.  
  230.         if (cp->bcode < 0)
  231.             continue;
  232.  
  233.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  234.             if (ip->next == cp->last) {
  235.                 ip->next = NULL;
  236.                 break;
  237.             }
  238.         }
  239.         free(cp->last->src.astr);
  240.         free(cp->last);
  241.  
  242.         if (cp->first == cp->last)
  243.             cp->first = cp->last = NULL;
  244.         else
  245.             cp->last = ip;
  246.         /*
  247.          * If the branch was unconditional, we want to represent
  248.          * it as a "fall through", so fix the pointers to do that.
  249.          */
  250.         if (cp->bcode == BRA) {
  251.             s_bdel++;
  252.             cp->bfall = cp->bcond;
  253.             cp->bcond = NULL;
  254.         }
  255.     }
  256. }
  257.  
  258. /*
  259.  * bclean() - remove references to empty blocks
  260.  *
  261.  * Called after bsplit() and bfix().
  262.  */
  263. static    void
  264. bclean(bp)
  265. register BLOCK    *bp;
  266. {
  267.     register BLOCK    *cp;
  268.  
  269.     /*
  270.      * First clean up references to empty blocks
  271.      */
  272.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  273.         if (cp->bcond != NULL)
  274.             cp->bcond = cblock(cp->bcond);
  275.         if (cp->bfall != NULL)
  276.             cp->bfall = cblock(cp->bfall);
  277.     }
  278.  
  279.     /*
  280.      * Now there are generally blocks that are still linked by the
  281.      * 'chain' pointers, but no longer referenced through 'bcond'
  282.      * or 'bfall' pointers. They don't actually need to be deleted
  283.      * since they won't cause trouble anywhere else.
  284.      */
  285. }
  286.  
  287. #if 0
  288. /*
  289.  * reachable(p1, p2) - is p2 reachable (with constraints) from p1
  290.  *
  291.  * Try to reach p2 from p1 by following the 'bfall' pointers, without
  292.  * going through a block that has already been touched. We stop searching
  293.  * after a while since this function doesn't have to be perfect, and we're
  294.  * mainly interested in improving small loops anyway.
  295.  */
  296. static    bool
  297. reachable(p1, p2)
  298. register BLOCK    *p1, *p2;
  299. {
  300.     register int    i;
  301.  
  302.     for (i=0; (i < 40) && (p1 != NULL) ;i++, p1 = p1->bfall) {
  303.  
  304.         if (TOUCHED(p1))
  305.             return FALSE;
  306.  
  307.         if (p1 == p2)
  308.             return TRUE;
  309.     }
  310.     return FALSE;
  311. }
  312. #endif
  313.  
  314. /*
  315.  * bwalk() - recursive walk through the branch graph
  316.  *
  317.  * Starting at the entry point, walk through the block graph placing
  318.  * blocks on the output list. By traversing the "bfall" nodes first
  319.  * we attempt to make blocks that fall through come in order so that
  320.  * branches are minimized.
  321.  *
  322.  * Joe describes this process as "grabbing the tree at the top and
  323.  * shaking".
  324.  *
  325.  * The 'lp' variable below maintains our position in the generated list
  326.  * of blocks.
  327.  */
  328. static    BLOCK    *lp;    /* pointer to the next block in the file */
  329.  
  330. static    bwalk(p)
  331. register BLOCK    *p;
  332. {
  333.     if (p == NULL || TOUCHED(p))
  334.         return;
  335.  
  336. #if 0
  337.     /*
  338.      * The following code still needs some work, so it is disabled
  339.      * for now...
  340.      */
  341.     /*
  342.      * Check to see if loop rotation is required. We "rotate" the loop
  343.      * by skipping the current node and traversing the 'bfall' node,
  344.      * and then the 'bcond' node. The function reachable() tells us
  345.      * that there's a loop through the 'bfall' nodes allowing us to
  346.      * make this optimization. The net result is that we try to move
  347.      * conditional branches to the bottoms of loops making the loop
  348.      * one instruction shorter. The overall number of branches remains
  349.      * the same.
  350.      *
  351.      * Rather than marking all the nodes again within the function
  352.      * "reachable", we just give up after a while if no loop is
  353.      * detected. This isn't perfect, but we get the biggest gain in
  354.      * small loops, and these will be detected accurately.
  355.      */
  356.     if (do_lrot && p->bcond != NULL && reachable(p->bfall, p)) {
  357.         s_lrot++;
  358.         bwalk(p->bfall);
  359.         bwalk(p->bcond);
  360.         return;
  361.     }
  362. #endif
  363.  
  364.     p->flags |= B_TOUCHED;
  365.     lp->next = p;
  366.     lp = lp->next;
  367.  
  368.     /*
  369.      * We should swap 'bfall' and 'bcond' and alter 'bcode' IF:
  370.      *
  371.      * 1. Both bfall and bcond are non-null.
  372.      * 2. The branch is a simple one (not a DBcc inst.)
  373.      * 3. Branch reversals are enabled.
  374.      * 4. The block at bfall has already been touched.
  375.      * 5. The block at bcond hasn't been touched.
  376.      *
  377.      * In this case, we can avoid an extra branch if we reverse the
  378.      * sense of the conditional branch, and swap the pointers.
  379.      */
  380.     if (p->bfall != NULL && p->bcond != NULL && p->bcode >= 0 &&
  381.         do_brev && TOUCHED(p->bfall) && !TOUCHED(p->bcond)) {
  382.         register BLOCK    *tmp;
  383.  
  384.         s_brev++;
  385.             tmp = p->bfall;
  386.             p->bfall = p->bcond;
  387.             p->bcond = tmp;
  388.             if ((p->bcode = bcomp(p->bcode)) < 0) {
  389.                 fprintf(stderr, "top: internal error in bwalk()\n");
  390.  
  391. /* CHANGED BY TETISOFT */
  392. /*                exit(1); */
  393.                 exit(EXIT_FAILURE);
  394.  
  395.             }
  396.     }
  397.     bwalk(p->bfall);
  398.     bwalk(p->bcond);
  399. }
  400.  
  401. /*
  402.  * bsort() - branch optimization
  403.  *
  404.  * Initialize and terminate the 'next' pointers before and after
  405.  * traversing the branch graph.
  406.  */
  407. static    void
  408. bsort(bp)
  409. register BLOCK    *bp;
  410. {
  411.     register BLOCK    *cb;
  412.  
  413.     lp = bp;
  414.  
  415.     bwalk(bp);    /* traverse the tree starting at the entry point */
  416.  
  417.     /*
  418.      * Now look for other parts of the tree that don't appear to be
  419.      * reachable, but really are. This can happen through the jump
  420.      * tables created for switch statements. For each such block,
  421.      * walk the subtree starting with it.
  422.      */
  423.     for (cb = bp; cb != NULL ;cb = cb->chain) {
  424.         if (!TOUCHED(cb) && (cb->flags & B_ISREACHED))
  425.             bwalk(cb);
  426.     }
  427.  
  428.     lp->next = NULL;
  429. }
  430.  
  431. /*
  432.  * bsetlab() - figure out which blocks really need labels
  433.  *
  434.  * This can be called AFTER bsort() to mark the blocks that are going to
  435.  * need labels. Anything that we're going to branch to later gets a label.
  436.  */
  437. static    void
  438. bsetlab(bp)
  439. register BLOCK    *bp;
  440. {
  441.     for (; bp != NULL ;bp = bp->next) {
  442.         if (bp->bcond != NULL)
  443.             cblock(bp->bcond)->flags |= B_LABEL;
  444.         if (bp->bfall != NULL && bp->bfall != bp->next)
  445.             cblock(bp->bfall)->flags |= B_LABEL;
  446.         /*
  447.          * If the block is reached via a jump table, then we
  448.          * need a label on THIS block directly.
  449.          */
  450.         if (bp->flags & B_ISREACHED)
  451.             bp->flags |= B_LABEL;
  452.     }
  453. }
  454.  
  455. /*
  456.  * bjoin() - join blocks that always come together
  457.  *
  458.  * If block 'b' always follows block 'a' unconditionally, then move the
  459.  * instructions in 'b' to the end of 'a', and remove 'b'. This allows us
  460.  * to do better peephole optimization since we can optimize sequences that
  461.  * used to span blocks.
  462.  */
  463. bjoin(bp)
  464. register BLOCK    *bp;
  465. {
  466.     BLOCK    *np, *bnext;
  467.  
  468.     for (; bp != NULL ;bp = bnext) {
  469.         bnext = bp->next;
  470.  
  471.         /*
  472.          * First block can't end with a conditional branch.
  473.          */
  474.         if (bp->bcond != NULL)
  475.             continue;
  476.  
  477.         /*
  478.          * Block must fall through to the next thing in the file.
  479.          */
  480.         if (bp->next == NULL || bp->next != bp->bfall)
  481.             continue;
  482.  
  483.         np = bp->next;
  484.  
  485.         /*
  486.          * Second block can't be the destination of a branch.
  487.          */
  488.         if (np->flags & B_LABEL)
  489.             continue;
  490.  
  491.         /*
  492.          * Join the blocks...
  493.          */
  494.         if (np->first != NULL)
  495.             np->first->prev = bp->last;
  496.  
  497.         if (bp->last != NULL)
  498.             bp->last->next = np->first;
  499.         else {
  500.             bp->first = np->first;
  501.             bp->last = np->last;
  502.         }
  503.  
  504.         if (np->flags & B_RET)
  505.             bp->flags |= B_RET;
  506.  
  507.         bp->last = np->last;
  508.         bp->bfall = np->bfall;
  509.         bp->bcond = np->bcond;
  510.         bp->bcode = np->bcode;
  511.         bp->next = np->next;
  512.  
  513.         /*
  514.          * Fix pointers so we don't free the instructions
  515.          * twice later on.
  516.          */
  517.         np->first = NULL;
  518.         np->last = NULL;
  519.  
  520.         /*
  521.          * If we've done a join, then we want to loop again on
  522.          * the current block to see if any others can be joined.
  523.          */
  524.         bnext = bp;
  525.     }
  526. }
  527.  
  528. /*
  529.  * bopt() - coordinates branch optimization for the given function
  530.  */
  531. void
  532. bopt(bp)
  533. register BLOCK    *bp;
  534. {
  535.     bsplit(bp);
  536.     bfix(bp);
  537.     bclean(bp);
  538.     bsort(bp);
  539.     bsetlab(bp);
  540.     bjoin(bp);
  541. }
  542.